//
// Created by 谢哲 on 2021/5/20.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;


int main() {
    double ln2 = log(2);
    int n, q;
    cin >> n >> q;
    int total_n = int(log(n) / ln2 + 1);

    vector<int> h(n);
    for (auto &p: h) cin >> p;

    vector<vector<int>> st_max(n, vector<int>(total_n, 0)), st_min(n, vector<int>(total_n, 0));
    for (int i=0;i<n;++i) {
        st_max[i][0] = h[i], st_min[i][0] = h[i];
    }
    for (int k=1;k<total_n;++k) {
        for (int i=0; i+(1<<k)<=n; ++i) {
            st_max[i][k] = max(st_max[i][k-1], st_max[i+(1<<(k-1))][k-1]);
            st_min[i][k] = min(st_min[i][k-1], st_min[i+(1<<(k-1))][k-1]);
        }
    }

    for (;q;--q) {
        int a, b;
        cin >> a >> b;
        --a;
        int len = b - a;
        int log_len = int(log2(len));
        int min_h = min(st_min[a][log_len], st_min[b-(1<<log_len)][log_len]);
        int max_h = max(st_max[a][log_len], st_max[b-(1<<log_len)][log_len]);
        cout << max_h - min_h << "\n";
    }

    return 0;
}